/**
 * 方法1：嵌套循环
 * O(n^2) 不推荐
*/
function findTowNumbers1 (arr: number[], n: number): number[] {
  const res: number[] = []
  const length = arr.length

  if (length === 0) return res
  // O(n^2)
  for (let i = 0; i < length - 1; i++) {
    const n1 = arr[i]
    let flag = false // 是否得到了结果
    for (let j = i + 1; j < length; j++) {
      const n2 = arr[j]
      if (n1 + n2 === n) {
        res.push(n1)
        res.push(n2)
        flag = true
        break
      }
    }
    if (flag) break
  }
  return res
}

/**
 * 方法2：双指针
 * O(n) 推荐！
 * 定义i指向头，j指向尾，求arr[i] + arr[j]
 * 如果大于n，则j需要向前移动
 * 如果小于n，则i需要向后移动
*/ 
function findTowNumbers2 (arr: number[], n: number): number[] {
  const res: number[] = []
  const length = arr.length

  if (length === 0) return res
  let i = 0 // 头
  let j = length - 1 // 尾
  while (i < j) {
    const n1 = arr[i]
    const n2 = arr[j]
    const sum = n1 + n2
    if (sum > n) {
      // sum 大于 n，则 j 要向前移动
      j--
    } else if (sum < n) {
      // sum 小于 n，则 i 要向后移动
      i++
    } else {
      // 相等
      res.push(n1)
      res.push(n2)
      break
    }
  }

  return res
}